﻿/*
 * Malte Frerichs
 * Melvin Bos
 * Jasper ter Weeme
 */

using System;
using System.Collections.Generic;

namespace SortOf
{
    public class QuickSort : ISort
    {
        private void Sort<T>(IList<T> list, int left, int right) where T : IComparable<T>
        {
            int i = left;
            int j = right;

            // we nemen als Pivot het middelste item
            T pivot = list[(left + right) / 2];

            while (i <= j)
            {
                // vergelijk waarde aan de linkerkant met de Pivot
                while (list[i].CompareTo(pivot) < 0)
                {
                    i++;    // schuif linker selector een op naar rechts
                }

                // vergelijk waarde aan de rechterkant met de Pivot
                while (list[j].CompareTo(pivot) > 0)
                {
                    j--;    // schuif rechters selector een op naar links
                }

                if (i <= j)
                {
                    // swap
                    T tmp = list[i];
                    list[i] = list[j];
                    list[j] = tmp;

                    i++;
                    j--;
                }
            }

            if (left < j)
            {
                Sort(list, left, j);
            }

            if (i < right)
            {
                Sort(list, i, right);
            }
        }

        public void Apply<T>(IList<T> list) where T : IComparable<T>
        {
            Sort(list, 0, list.Count - 1);
        }
    }
}
